Management techniques of finite resources, such as communications links, often involve sharing the resource among a number of consumers. Consumers may include various devices, classes of traffic, flows, persons, or any other criteria that distinguishes among uses of the shared resource. When resources are shared, decisions are made as to which consumer will be permitted to use the resource when more than one consumer requires its use.
Known policies for distributing access to the shared resource include round robin scheduling algorithms and priority arbiters. In some instances, it is desirable to share the resource in a disproportionate manner such that all consumers of the resource receive a share of the available capacity but a subset of those consumers receive larger or smaller shares than the others. In the context of communication links, an amount of bandwidth can be allocated to particular consumers and groups of consumers according to their Quality-of-Service (QoS) subscription levels or priorities. Bandwidth allocation allows a port on a network device to guarantee a certain rate of throughput to an end device via a communication link.
Some methodologies for disproportionate sharing of resources use a system of credits in which each consumer is periodically allocated a number of credits proportionate to the consumer's share. The credits are decremented each time the consumer uses the resource. In the case of bandwidth allocation of the communications link, credits of the consumer are decremented when a packet of the consumer is transmitted. The shares of each consumer, however, are often times fixed and cannot be modified.
Other implementations permit the shares to be changed, but the cost to implement is high. Credits are typically reapportioned among active consumers of the resource, leaving out inactive consumers. Typical methodologies require the credits granted to each active consumer during reapportionment to be normalized to retain the desired ratios among active consumers when not all consumers are active. Normalization generally involves dividing the allocation of credits of each active consumer by the sum of the allocations for all active consumers. Arbitration is then performed based on the number of credits for each consumer. In the context of network devices, such as switches, such a division operation is prohibitively expensive to implement in hardware and may cause computational delays which dampens performance when high speed operation is desired.
Weighted round robin (WRR) is an integer-based scheduling algorithm that can be used to implement disproportionate sharing of the resource. WRR uses the weight assigned to a consumer to make the scheduling decision. The bandwidth allocated to a consumer is proportional to the weight of that consumer and inversely proportional to the total weight of all active consumers. In some instances, lower priority consumers are deprived from obtaining the requested bandwidth in the network connection, for example where a higher priority consumer having a large-sized packet occupies all available bandwidth.